package com.zwxu.list;

public class ReverseLinkedListDemo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		//ListNode temp = node1;
		ListNode temp = reverse2(node1);
		while(temp != null){
			System.out.print(temp.val+">");
			temp = temp.next;
			
		}

	}
	
	 public static ListNode reverse(ListNode head) {
		 if (head == null || head.next == null) {  
	            return head;// 若为空链或者当前结点在尾结点，则直接还回  
	     }  
		 ListNode sHead = reverse(head.next);
		 head.next.next = head;
		 head.next = null;
		 return sHead;
	 }
	 
	 /** 
	     * 遍历，将当前节点的下一个节点缓存后更改当前节点指针 
	     */  
	    public static ListNode reverse2(ListNode head) {  
	        if (head == null)  
	            return head;  
	        ListNode pre = head;// 上一结点  
	        ListNode cur = head.next;// 当前结点  
	        ListNode tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）  
	        while (cur != null) {// 当前结点为null，说明位于尾结点  
	            tmp = cur.next;  
	            cur.next = pre;// 反转指针域的指向  
	  
	            // 指针往下移动  
	            pre = cur;  
	            cur = tmp;  
	        }  
	        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点  
	        head.next = null;  
	          
	        return pre;  
	    }  

}
